package org.niu.backtracking;

import java.util.ArrayList;
import java.util.Arrays;

public class SubSets {

    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<Integer> list = new ArrayList<>();
        backTracking(S,list,0);
        return ans;
    }
    void backTracking(int[] S,ArrayList<Integer> list,int index){
        ans.add(new ArrayList<>(list));
        if(index >= S.length-1) return;
        for (int i = index; i < S.length; i++) {
            list.add(S[index]);
            backTracking(S,list,i+1);
            list.remove(list.size()-1);
        }
    }
}
